#!/usr/bin python3
# -*- coding: utf-8 -*-
from math import inf
from typing import List, Dict


class MaxPQ:
    """优先队列"""

    _pq: List[Node]

    def __init__(self):
        self._pq = [inf]
        self._N = 0

    def exch(self, i: int, j: int):
        self._pq[i], self._pq[j] = self._pq[j], self._pq[i]

    def less(self, i: int, j: int) -> bool:
        return self._pq[i].key() < self._pq[j].key()

    def swim(self, i: int):
        """堆有序的上浮算法"""
        while i > 1 and self.less(i // 2, i):
            self.exch(i // 2, i)
            i = i // 2

    def sink(self, i: int):
        """堆有序的下沉算法"""
        while 2 * i < self._N:
            j = 2 * i
            if j < self._N and self.less(j, j + 1):
                j += 1
            if self.less(i, j):
                self.exch(i, j)
                i = j

    def del_max(self) -> Node:
        node = self._pq[1]
        self.exch(1, self._N)
        self._N -= 1
        self.sink(1)
        self._pq.pop(-1)
        return node

    def insert(self, node: Node):
        self._pq.append(node)
        self._N += 1
        self.swim(self._N)

    def heap_sort(self):

        while self._N > 1:
            self.exch(1, -1)
            self._N -= 1
            self.sink(1)
        return self._pq.copy()

    class Node(object):
        left: Node
        right: Node

        def __init__(self, key, val, n: int):
            self._key = key
            self._val = val
            self._n = n

        def key(self):
            return self._key

        def val(self):
            return self._val
